#define _CRT_SECURE_NO_WARNINGS
//#include<stdio.h>
//
//int fac(int x)
//{
//	if (x <= 2)
//		return 1;
//	else
//		return (fac(x - 1) + fac(x - 2));
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = fac(n);
//	printf("%d\n", ret);
//	return 0;
//}

//#include<stdio.h>
//
//int fac(int x)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (x > 2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		x--;
//	}
//	return c;
//}
//
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = fac(n);
//	printf("%d\n", ret);
//	return 0;
//}

//#include<stdio.h>
//
//int fac(int x)
//{
//	if (x == 1)
//		return 1;
//	else
//		return (x * fac(x - 1) );
//}
//
//
//int main()
//{
//	int num = 0;
//	scanf("%d", &num);
//	int ret = fac(num);
//	printf("%d\n", ret);
//	return 0;
//}

//#include<stdio.h>
//
//int Digitim(int x)
//{
//	if (x < 10)
//		return x % 10;
//	else
//		return (Digitim(x / 10) + (x % 10));
//}
//
//int main()
//{
//	int num = 0;
//	scanf("%d", &num);
//	int ret = Digitim(num);
//	printf("%d", ret);
//	return 0;
//}


//#include<stdio.h>
//
//int my_strlen(char* p)
//{
//	if (*p != '\0')
//		return (1 + my_strlen(++p));
//	return 0;
//}
//
//void  reverse_string(char* string)
//{
//	int n = my_strlen(string);
//	if (*string != '\0')
//	{
//		int temp = *string;
//		*string = *(string + (n - 1));
//		*(string + (n - 1)) = '\0';
//		reverse_string(string + 1);
//		*(string + (n - 1)) = temp;
//	}
//}
//
//int main()
//{
//	char ch[20] = {0};
//	scanf("%s", ch);
//	/*int c = my_strlen(ch);
//	printf("%d", c);*/
//	reverse_string(ch);
//	printf("%s", ch);
//	return 0;
//}

//#include<stdio.h>
//
//int my_strlen1(char* p)
//{
//	if (*p != '\0')
//		return (1 + my_strlen1(++p));
//	return 0;
//}
//
//int my_strlen2(char* p)
//{
//	int count = 0;
//	while (*p != '\0')
//	{
//		count++;
//		++p;
//	}
//	return count;
//}
//
//int main()
//{
//	char ch[20] = { 0 };
//	scanf("%s", ch);
//	int n = my_strlen1(ch);
//	int m = my_strlen2(ch);
//	printf("%d %d\n", n, m);
//}


//#include<stdio.h>
//
//double my_pow(int x, int y)
//{
//	if (y == 1)
//		return x;
//	else if(y > 1)
//	{
//		return (x * my_pow(x, --y));
//	}
//	else
//	{
//		return ((1.0 / x) * my_pow(x, ++y));
//	}
//
//}
//
//int main()
//{
//	int n = 0;
//	int k = 0;
//	scanf("%d %d", &n, &k);
//	double ret = my_pow(n, k);
//	printf("%.2lf\n", ret);
//	return 0;
//}

//#include<stdio.h>
//
//int fac(int x)
//{
//	if (x == 1)
//		return 1;
//	else
//		return (x * fac(x - 1) );
//}
//
//int fac1(int x)
//{
//	int ret = 1;
//	int i = 1;
//	for (i = 1; i <= x; i++)
//	{
//		ret *= i;
//	}
//	return ret;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int x = fac(n);
//	int y = fac1(n);
//	printf("%d %d", x, y);
//	return 0;
//}

//#include<stdio.h>
//
//void print(int x)
//{
//	if (x > 9)
//		print(x / 10);
//	printf("%d ", x % 10);
//}
//
//int main()
//{
//	int num = 0;
//	scanf("%d", &num);
//	print(num);
//	return 0;
//}